package com.xsherl.leetcode.solution;

import com.xsherl.leetcode.base.TreeNode;
import com.xsherl.leetcode.utils.PrintUtils;

public class BalancedBinaryTree {

    /**
     *  高度平衡二叉树定义为：一个二叉树每个节点 的左右两个子树的高度差的绝对值不超过 1 。
     */
    public boolean isBalanced(TreeNode root) {
        if (root == null){
            return true;
        }
        int left = getHeight(root.left);
        int right = getHeight(root.right);
        if (Math.abs(left - right) > 1){
            return false;
        }
        return isBalanced(root.left) && isBalanced(root.right);
    }
    public int getHeight(TreeNode root) {
        if (root == null){
            return 0;
        }
        int leftHeight = getHeight(root.left);
        int rightHeight = getHeight(root.right);
        return Math.max(leftHeight, rightHeight) + 1;
    }

    public static void main(String[] args) {
        TreeNode root = TreeNode.buildTree(1,2,2,3,null,null,3,4,null,null,4);
        PrintUtils.println(root);
        boolean balanced = new BalancedBinaryTree().isBalanced(root);
        System.out.println(balanced);
    }
}
